package model;



import java.util.Stack;




public class PostOrderTraversal {

	private Stack<NamedTreeNode> nodePath;
	
	private NamedTreeNode root;

	/**
	 * 
	 * @param root
	 */
	public PostOrderTraversal(NamedTreeNode root){
		
		
		// INORDER
		this.root = root;
		nodePath = new Stack<NamedTreeNode>();
		traverse();
		
		
	
	}
	
	/**
	 * 
	 * @param root
	 */
	public void traverse() {
		NamedTreeNode current = this.root;
		
		while( current != null || !nodePath.isEmpty() ){
			if ( current != null){
				nodePath.push(current);
				current = (NamedTreeNode) current.getChildAt(NamedTreeNode.LEFT);
			}else{
				current = this.nodePath.pop();
				current.visit();
				System.out.println(current.toString());
				
				if( (current = this.nodePath.pop() ).secondPop()){
					nodePath.push(current);
					current = null;
				}else{
					current.visit();
					nodePath.push(current);
					current = (NamedTreeNode) current.getChildAt(NamedTreeNode.RIGHT);
					
				}
			
			}
		}
	}	
	
//	/** Iteratively traverses the binary tree in post-order */
//	public void postorder( ) {
//	    if( root == null ) return;
//	 
//	    Stack<Node> stack = new Stack<Node>( );
//	    Node current = root;
//	 
//	    while( true ) {
//	 
//	        if( current != null ) {
//	            if( current.right != null ) stack.push( current.right );
//	            stack.push( current );
//	            current = current.left;
//	            continue;
//	        }
//	 
//	        if( stack.isEmpty( ) ) return;
//	        current = stack.pop( );
//	 
//	        if( current.right != null && ! stack.isEmpty( ) && current.right == stack.peek( ) ) {
//	            stack.pop( );
//	            stack.push( current );
//	            current = current.right;
//	        } else {
//	            System.out.print( current.data + " " );
//	            current = null;
//	        }
//	    }
	
//	// POSTORDER
//	current = root; // Begin bij de root
//	while ( current is not NULL or stack is nonempty )
//	 if ( current is not NULL ){
//	  // zelf aanvullen, 2 regels
//	 } 
//	 else {
//	  current = pop
//	  if ( current.secondPop ){
//	   // zelf aanvullen, 2 regels
//	  } 
//	  else{
//	   // zelf aanvullen, 3 regels
//	  }
//	 }
	
	
	
}
